package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/deepest-leaves-sum/'>层数最深叶子节点的和(Deepest Leaves Sum)</a>
 * <p>给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
 *                      1
 *                    /  \
 *                   2    3
 *                 /  \    \
 *                4    5    6
 *               /           \
 *              7             8
 *      输出：15
 *
 * 示例 2：
 *      输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
 *                      6
 *                    /   \
 *                   7     8
 *                 /  \  /  \
 *                2   7 1    3
 *               /   / \      \
 *              9   1  4       5
 *      输出：19
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>树中节点数目在 [1, 10^4] 之间</li>
 *     <li>1 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/23 14:41
 */
public class LC1302DeepestLeavesSum_M {

    static class Solution {
        public int deepestLeavesSum(TreeNode root) {
            int ans = 0;
            if (root == null) {
                return ans;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeSum = 0;
                int currLevelNodeSize = queue.size();
                for (int i = 0; i < currLevelNodeSize; i++) {
                    TreeNode currNode = queue.poll();
                    currLevelNodeSum += currNode.val;
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                    ans = currLevelNodeSum;
                }
            }
            return ans;
        }

        /**
         * 最大层数
         */
        int maxLevel = 0;
        /**
         * 结果
         */
        int ans = 0;

        public int deepestLeavesSum2(TreeNode root) {
            dfs(root, 1);
            return ans;
        }

        public void dfs(TreeNode currNode, int currLevel) {
            if (currNode == null) {
                return;
            }
            // 叶子节点
            if (currNode.left == null && currNode.right == null) {
                if (currLevel > maxLevel) {
                    maxLevel = currLevel;
                    ans = currNode.val;
                } else if (currLevel == maxLevel) {
                    ans += currNode.val;
                }
            }
            if (currNode.left != null) {
                dfs(currNode.left, currLevel + 1);
            }
            if (currNode.right != null) {
                dfs(currNode.right, currLevel + 1);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.right = new TreeNode(3);
        root1.left.left = new TreeNode(4);
        root1.left.left.left = new TreeNode(7);
        root1.left.right = new TreeNode(5);
        root1.right.right = new TreeNode(6);
        root1.right.right.right = new TreeNode(8);

        Solution solution1 = new Solution();
        System.out.println(solution1.deepestLeavesSum(root1));

        TreeNode root2 = new TreeNode(6);
        root2.left = new TreeNode(7);
        root2.right = new TreeNode(8);
        root2.left.left = new TreeNode(2);
        root2.left.right = new TreeNode(7);
        root2.right.left = new TreeNode(1);
        root2.right.right = new TreeNode(3);
        root2.left.left.left = new TreeNode(9);
        root2.left.right.left = new TreeNode(1);
        root2.left.right.right = new TreeNode(4);
        root2.right.right.right = new TreeNode(5);

        Solution solution2 = new Solution();
        System.out.println(solution2.deepestLeavesSum(root2));
    }
}
